{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #House Robber II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rob"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #打家劫舍 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 <strong>围成一圈</strong> ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，<strong>如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警</strong> 。</p>\n",
    "\n",
    "<p>给定一个代表每个房屋存放金额的非负整数数组，计算你 <strong>在不触动警报装置的情况下</strong> ，今晚能够偷窃到的最高金额。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,2]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,1]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。\n",
    "&nbsp;    偷窃到的最高金额 = 1 + 3 = 4 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [house-robber-ii](https://leetcode.cn/problems/house-robber-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [house-robber-ii](https://leetcode.cn/problems/house-robber-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,2]', '[1,2,3,1]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        def judge(chessboard: List[List[str]], x: int, y: int, dx: int, dy: int) -> bool:\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/fHi6rV/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        def bfs(chessboard, px, py):\n",
    "            cnt = 0\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = 'X'\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for dx in (-1, 0, 1):\n",
    "                    for dy in (-1, 0, 1):\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, x, y, dx, dy):\n",
    "                            tx = x + dx\n",
    "                            ty = y + dy\n",
    "                            while chessboard[tx][ty] != 'X':\n",
    "                                cnt += 1\n",
    "                                q.append((tx, ty))\n",
    "                                chessboard[tx][ty] = 'X'\n",
    "                                tx += dx\n",
    "                                ty += dy\n",
    "            return cnt\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if chessboard[i][j] == '.':\n",
    "                    ans = max(ans, bfs(chessboard, i, j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "\n",
    "class MyCalendar:\n",
    "    def __init__(self):\n",
    "        self.booked = SortedDict()\n",
    "\n",
    "    def book(self, start: int, end: int) -> bool:\n",
    "        i = self.booked.bisect_left(end)\n",
    "        if i == 0 or self.booked.items()[i - 1][1] <= start:\n",
    "            self.booked[start] = end\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/fi9suh/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:\n",
    "        n = len(books)\n",
    "        f = [0] + [inf] * n  # 在前面插入一个状态表示 dfs(-1)=0\n",
    "        for i in range(n):\n",
    "            max_h, left_w = 0, shelf_width\n",
    "            for j in range(i, -1, -1):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w < 0: break  # 空间不足，无法放书\n",
    "                max_h = max(max_h, books[j][1])  # 从 j 到 i 的最大高度\n",
    "                f[i + 1] = min(f[i + 1], f[j] + max_h)\n",
    "        return f[n]  # 翻译自 dfs(n-1)\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/filling-bookcase-shelves/solutions/2240688/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-0vg6/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # https://leetcode.cn/problems/find-a-good-subset-of-the-matrix/solutions/2304610/zhi-shang-ju-de-ti-jie-zheng-que-xing-zh-1wju/\n",
    "\n",
    "        \"\"\"\n",
    "        首先要注意到1 <= n <= 5这个数据量，划重点，后面会用到。\n",
    "        为了解释方便，我们称子集大小的一半为“标准”。\n",
    "\n",
    "        1. 首先讨论行子集只有1行时，此情况很简单，因为“标准”为0，所以必须有一行所有元素均为0，否则我们必须考虑选择更多的行来增大“标准”。\n",
    "\n",
    "        2. 当子集行数为2时，“标准”为1，所以要找到两行按列相加后所有元素都小于等于1的行，也就是说必须有两行进行“&”运算后结果为0。\n",
    "        如果找不出这样的两行，我们依然要考虑增加行数来增大“标准”。\n",
    "\n",
    "        3. 当子集行数为3时，其“标准”依然为1，但却要多出一行，完全不用考虑。\n",
    "        不考虑是指，能找到子集为3，为啥不在子集为2的场景时就退出寻找？都是标准为1。多加一行，只会增加列和\n",
    "        不仅行数为3时，所有行数为奇数时都会出现此情况，所以我们只需要考虑行数为偶数的子集。\n",
    "\n",
    "        4. 当子集行数为4时，其“标准”为2，要注意到我们之所以会考虑到将子集取四行，是因为当子集行数为2时，无法找出两行进行“&”运算后结果为0的行，\n",
    "        也就是说，将任意两行按列相加，都至少会出现一个2，那么子集行数为4时，能找出多少个2？\n",
    "        根据组合数的知识，在4行中选2行有6种选法，所以至少会出现6个2，但是1 <= n <= 5，所以必然会有一列之和大于2，\n",
    "        所以当子集行数为2时不行，那么子集行数为4时依然不行。不仅子集行数为4不行，接下来所有更大的偶数都不行,证明方法同理。\n",
    "\n",
    "        所以可以得到结论，如果子集取1行2行都不行，那么就不存在满足条件的取法，所以我们只需要考虑是否有一行元素全部为0，\n",
    "        或者可以找出两行进行“&”运算后结果为0。\n",
    "\n",
    "        \"\"\"\n",
    "        idx = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j, x in enumerate(row):\n",
    "                mask |= x << j\n",
    "            idx[mask] = i\n",
    "\n",
    "        # 有一行都是0，满足子集行数为1，”标准“为0的场景\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "\n",
    "        # 两两之间加起来不大于1，满足子集行数2，”标准“为1的场景\n",
    "        for x, i in idx.items():\n",
    "            for y, j in idx.items():\n",
    "                if (x & y) == 0:\n",
    "                    return sorted([i, j])\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "            \n",
    "        g = defaultdict(list)\n",
    "        deg = {}\n",
    "        for r, ing in zip(recipes, ingredients):\n",
    "            for s in ing:\n",
    "                g[s].append(r)  # 从这道菜的原材料向这道菜连边\n",
    "            deg[r] = len(ing)\n",
    "        ans = []\n",
    "        q = deque(supplies)  # 拓扑排序（用初始原材料当队列）\n",
    "        while q:\n",
    "            for r in g[q.popleft()]:\n",
    "                deg[r] -= 1\n",
    "                if deg[r] == 0:  # 这道菜的所有原材料我们都有\n",
    "                    q.append(r)\n",
    "                    ans.append(r)\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/find-all-possible-recipes-from-given-supplies/solutions/1176904/go-tuo-bu-pai-xu-by-endlesscheng-lnlg/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob_helper(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0: return 0\n",
    "        if len(nums) <= 2: return max(nums)\n",
    "        \n",
    "        rob_list = [nums[0], max(nums[:2])]\n",
    "        for i in range(2, len(nums)):\n",
    "            rob_list.append(max(rob_list[i-1], nums[i] + rob_list[i-2]))\n",
    "        return rob_list[-1]\n",
    "        \n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0: return 0\n",
    "        if len(nums) <= 3: return max(nums)\n",
    "        \n",
    "        return max(self.rob_helper(nums[:-1]), self.rob_helper(nums[1:]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef rob(self, nums):\n",
    "\t\t\"\"\"\n",
    "\t\t:type nums: List[int]\n",
    "\t\t:rtype: int\n",
    "\t\t\"\"\"\n",
    "\t\tif len(nums) <= 1:\n",
    "\t\t\treturn nums[0] if nums else 0\n",
    "\t\t\t\n",
    "\t\tdp = [0 for i in range(len(nums))]\n",
    "\t\tdp[0] = nums[0]\n",
    "\t\tfor i in range(1, len(nums) - 1):\n",
    "\t\t\tdp[i] = max(dp[i-1], (0 if i == 1 else dp[i-2] + nums[i]))\n",
    "\t\tres1 = dp[len(nums) - 2]\n",
    "\t\t\n",
    "\t\tdp[0] = 0\n",
    "\t\tfor i in range(1, len(nums)):\n",
    "\t\t\tdp[i] = max(dp[i-1], (nums[i] if i == 1 else dp[i-2] + nums[i]))\n",
    "\t\t\t\n",
    "#\t\tprint(dp[len(nums) - 1])\n",
    "\t\t\n",
    "\t\treturn max(dp[len(nums) - 1], res1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        arr = [0 for _ in range(len(nums) + 2)]\n",
    "        for i in range(len(nums)):\n",
    "            if i == len(nums) - 1:\n",
    "                arr[i + 2] = max(arr[i + 1], nums[i] + self.rerob(nums[1:-2]))\n",
    "            else:\n",
    "                arr[i + 2] = max(arr[i + 1], nums[i] + arr[i])\n",
    "        return arr[-1]\n",
    "\n",
    "\n",
    "    def rerob(self, nums):\n",
    "        arr = [0 for _ in range(len(nums) + 2)]\n",
    "        for i in range(len(nums)):\n",
    "            arr[i + 2] = max(arr[i + 1], nums[i] + arr[i])\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        dp = [[nums[i] if j == i else 0 for j in range(n)] for i in range(n)]\n",
    "        ret = max(nums)\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j] = max(dp[i][j], dp[i][j-1] if j > i else 0, dp[i+1][j] if j > i else 0, dp[i][j-2] + nums[j] if j - 2 >= i else 0, dp[i+2][j] + nums[i] if i + 2 <= j else 0)\n",
    "        #print(dp, dp[1][n-1], dp[0][n-2])\n",
    "        return max(ret, dp[1][n-1] if n > 1 else 0, dp[0][n-2] if n > 1 else 0)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) == 0: return 0\n",
    "        if len(nums) == 1: return nums[0]\n",
    "        def helper(start, end):\n",
    "            pre1, pre2 = 0, 0\n",
    "            for i in range(start, end+1):\n",
    "                pre1, pre2 = max(pre1, pre2+nums[i]), pre1\n",
    "            return pre1\n",
    "        return max(helper(0, len(nums)-2), helper(1, len(nums)-1))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n == 0: return 0\n",
    "        if n < 4: return max(nums)\n",
    "\n",
    "        first, second = 0, 0\n",
    "        for i in nums[:-1]: \n",
    "            first, second = second, max(first + i, second)\n",
    "            print(first,second)\n",
    "        result = second\n",
    "\n",
    "        first, second = 0, 0\n",
    "        for i in nums[1:]: \n",
    "            first, second = second, max(first + i, second)\n",
    "            print(first,second)\n",
    "        return max(result, second)\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        dp1 = [0]*len(nums)\n",
    "        dp2 = [0]*len(nums)\n",
    "        for i in range(0,len(nums)-1):\n",
    "            if i == 0:\n",
    "                dp1[i] = nums[i]\n",
    "            elif i == 1:\n",
    "                dp1[i] = max(nums[i],nums[i-1])\n",
    "            else:\n",
    "                dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i])\n",
    "        for j in range(1,len(nums)):\n",
    "            if j == 1:\n",
    "                dp2[j] = nums[j]\n",
    "            elif j == 2:\n",
    "                dp2[j] = max(nums[j],nums[j-1])\n",
    "            else:\n",
    "                dp2[j] = max(dp2[j-1],dp2[j-2]+nums[j])\n",
    "        print(dp1,dp2)\n",
    "        return max(dp1[-2],dp2[-1])\n",
    "            \n",
    "        \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return nums[0]\n",
    "        return max(self.helper(0,n-2,nums),self.helper(1,n-1,nums))\n",
    "\n",
    "    # 求[start,end]之间能偷的最大价值\n",
    "    def helper(self, start, end,nums):\n",
    "        n = end - start + 1\n",
    "        memo = [0] * (n + 2)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            memo[i] = max(nums[i+start] + memo[i + 2], memo[i + 1])\n",
    "        return memo[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#nums[begin, end)\n",
    "def rob(nums, begin, end):\n",
    "    size = end - begin\n",
    "    if size == 0:\n",
    "        return 0\n",
    "    if size == 1:\n",
    "        return nums[begin]\n",
    "    if size == 2:\n",
    "        return max(nums[begin], nums[begin + 1])\n",
    "        \n",
    "    pre_include = nums[begin + 1]\n",
    "    pre_total = max(nums[begin], nums[begin + 1])\n",
    "    prepre_total = nums[begin]\n",
    "        \n",
    "    total = -1;\n",
    "\n",
    "    for i in range(begin + 2, end):\n",
    "        include = prepre_total + nums[i]\n",
    "        temp = max(pre_include, include)\n",
    "        pre_include = include\n",
    "        prepre_total = pre_total\n",
    "        pre_total = temp\n",
    "        total = temp\n",
    "    return total\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        size = len(nums)\n",
    "        if size == 0:\n",
    "            return 0\n",
    "        if size < 4:\n",
    "            return max(nums)\n",
    "        a = rob(nums, 1, size) # do not rob #1house\n",
    "        b = nums[0] + rob(nums, 2, size - 1) # rob #1house\n",
    "        return max(a,b)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        if len(nums) == 2:\n",
    "            return max(nums[0], nums[1])\n",
    "        dp1 = [0 for i in range(len(nums))]\n",
    "        dp2 = [0 for i in range(len(nums))]\n",
    "        dp1[0] = nums[0]\n",
    "        dp1[1] = max(nums[0], nums[1])\n",
    "        dp2[0] = nums[1]\n",
    "        dp2[1] = max(nums[1], nums[2])\n",
    "        for i in range(2, len(nums)-1):\n",
    "            dp1[i] = max(dp1[i-2]+nums[i], dp1[i-1])\n",
    "            dp2[i] = max(dp2[i-2]+nums[i+1], dp2[i-1])\n",
    "        return max(max(dp1), max(dp2))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        if len(nums) == 2:\n",
    "            return max(nums[0], nums[1])\n",
    "        dp1 = [0 for i in range(len(nums)-1)]\n",
    "        dp2 = [0 for i in range(len(nums)-1)]\n",
    "        dp1[0] = nums[0]\n",
    "        dp1[1] = max(nums[0], nums[1])\n",
    "        dp2[0] = nums[1]\n",
    "        dp2[1] = max(nums[1], nums[2])\n",
    "        for i in range(2, len(nums)-1):\n",
    "            dp1[i] = max(dp1[i-2]+nums[i], dp1[i-1])\n",
    "            dp2[i] = max(dp2[i-2]+nums[i+1], dp2[i-1])\n",
    "        return max(max(dp1), max(dp2))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        因为是环， 第一间和第二间房子不能同时被偷\n",
    "        情况1： 第一家偷了， 也就是偷 0, i-1 之间的最大金额\n",
    "        情况2： 第一家不偷   也就是偷 1, i 之间的最大金额\n",
    "        情况3： 第一和最后一家都不偷， 也就是偷 1, i-1 之间的最大金额\n",
    "          情况三的选择一定小于情况1 和2， 所以我们只比较情况1，2 结构即可\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        def _rob(rnums):\n",
    "            n = len(rnums)\n",
    "            dp = [0] * (n + 2)\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                dp[i] = max(dp[i + 1], dp[i + 2] + rnums[i])\n",
    "            return dp[0]\n",
    "            \n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        return max(_rob(nums[:len(nums) - 1]), _rob(nums[1:]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) < 4:\n",
    "            return max(nums) \n",
    "\n",
    "        ans = 0\n",
    "        dp = [0] * (len(nums) - 1)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(1, len(nums) - 2):\n",
    "            dp[i+1] = max(dp[i], nums[i+1] + dp[i-1])\n",
    "        ans = max(ans, dp[-1])\n",
    "\n",
    "        dp[0] = nums[1]\n",
    "        dp[1] = max(nums[1], nums[2])\n",
    "        for i in range(2, len(nums) - 1):\n",
    "            dp[i] = max(dp[i-1], nums[i+1] + dp[i-2])\n",
    "        ans = max(ans, dp[-1])\n",
    "        return ans\n",
    "\n",
    "        '''di = {}\n",
    "\n",
    "        def dfs(nums):\n",
    "            if len(nums) == 0:\n",
    "                return 0\n",
    "            if len(nums) == 1:\n",
    "                return nums[0]\n",
    "            if tuple(nums) in di:\n",
    "                return di[tuple(nums)]\n",
    "            ans = nums[0] + dfs(nums[2:-1])\n",
    "            for i in range(1, len(nums)-1):\n",
    "                ans = max(ans, nums[i] + dfs(nums[:i-1] + nums[i+2:]))\n",
    "            ans = max(ans, nums[-1] + dfs(nums[1:-2]))\n",
    "            di[tuple(nums)] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dfs(nums)'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        lastmax1=0\n",
    "        lastmax2=0\n",
    "        size=len(nums)\n",
    "\n",
    "        if size>1:\n",
    "            lis1=[nums[0]]*size\n",
    "            lis2=[nums[-1]]*size\n",
    "            for i in range(1,size):\n",
    "                lis1[i]=max(lis1[i-1], lastmax1+nums[i])\n",
    "                lastmax1=lis1[i-1]\n",
    "                lis2[size-i-1]=max(lis2[size-i], lastmax2+nums[size-i-1])\n",
    "                lastmax2=lis2[size-i]\n",
    "            return max(lis1[-2], lis2[1])\n",
    "        elif size==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:return 0\n",
    "        if len(nums) == 1:return nums[0]\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        nums1 = nums[:-1]\n",
    "        nums2 = nums[1:]\n",
    "\n",
    "        def helper(nums):\n",
    "            if not nums:return 0\n",
    "\n",
    "            n = len(nums)\n",
    "\n",
    "            dp = [0]*n\n",
    "            dp[0] = nums[0]\n",
    "\n",
    "            for i in range(1,n):\n",
    "                if i == 1:\n",
    "                    dp[i] = max(nums[i],nums[i-1])\n",
    "                else:\n",
    "                    dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "            return dp[-1]\n",
    "        \n",
    "        return max(helper(nums1),helper(nums2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: [int]) -> int:\n",
    "        def my_rob(nums):\n",
    "            cur, pre = 0, 0\n",
    "            for num in nums:\n",
    "                cur, pre = max(pre + num, cur), cur\n",
    "            return cur\n",
    "        return max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums) > 1 else nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        def my_rob(nums):\n",
    "            if not nums:\n",
    "                return 0\n",
    "            if len(nums) == 1:\n",
    "                return nums[0]\n",
    "            dp = [0 for i in nums]\n",
    "            dp[0] = nums[0]\n",
    "            dp[1] = max(nums[0], nums[1])\n",
    "            for i in range(2, len(nums)):\n",
    "                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])\n",
    "            return dp[-1]\n",
    "        return max(my_rob(nums[1:]),my_rob(nums[:-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        last1, res1 = 0, 0\n",
    "        for n in nums[1:]:\n",
    "            last1, res1 = res1, max(last1+n, res1)\n",
    "        \n",
    "        last2, res2 = 0, 0\n",
    "        for n in nums[:-1]:\n",
    "            last2, res2 = res2, max(last2+n, res2)\n",
    "        \n",
    "        return max(res1, res2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob_base(self, nums):\n",
    "        length  = len(nums)\n",
    "        if length == 0:\n",
    "            return 0\n",
    "        elif length == 1:\n",
    "            return nums[0]\n",
    "        elif length == 2:\n",
    "            return max(nums[0], nums[1])\n",
    "        dp = list()\n",
    "        dp.extend([nums[0], max(nums[0], nums[1])])\n",
    "        for i in range(2, length):\n",
    "            dp.append(max(dp[-2]+nums[i], dp[-1]))\n",
    "        return max(dp[-1], dp[-2])\n",
    "\n",
    "    def rob(self, nums):\n",
    "            length = len(nums)\n",
    "            if length == 0:\n",
    "                return 0\n",
    "            elif length == 1:\n",
    "                return nums[0]\n",
    "            elif length == 2 or length == 3:\n",
    "                return max(nums)\n",
    "            nums1 = nums[:-1]\n",
    "            nums2 = nums[1:]\n",
    "            return max(self.rob_base(nums1), self.rob_base(nums2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        import functools\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def helper(start, end):\n",
    "            if start > end:\n",
    "                return 0\n",
    "            return max(helper(start + 1, end), # 不抢，去下家\n",
    "                       nums[start] + helper(start + 2, end)) # 抢，去下下家\n",
    "\n",
    "        return max(helper(0, n - 2), helper(1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:return nums[0]\n",
    "        memo = dict()\n",
    "        def dp1(i, current=True):\n",
    "            if i >= len(nums)-1:return 0\n",
    "            t = (i, current)\n",
    "            if t in memo:return memo[t]\n",
    "            memo[t] = 0\n",
    "            if current:\n",
    "                memo[t] = nums[i] + dp1(i+1,False)\n",
    "            else:\n",
    "                memo[t] = max(dp1(i+1,True), dp1(i+1,False))\n",
    "            return memo[t]\n",
    "\n",
    "        memo2 = dict()\n",
    "        def dp2(i, current=False):\n",
    "            if i >= len(nums):return 0\n",
    "            t = (i, current)\n",
    "            if t in memo2:return memo2[t]\n",
    "            memo2[t] = 0\n",
    "            if current:\n",
    "                memo2[t] = nums[i] + dp2(i+1,False)\n",
    "            else:\n",
    "                memo2[t] = max(dp2(i+1,True), dp2(i+1,False))\n",
    "            return memo2[t]\n",
    "        print(dp1(0, True))\n",
    "        print(dp2(0, False))\n",
    "        return max(dp1(0, True), dp2(0, False))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class memoize:\n",
    "    def __init__(self, f):\n",
    "        self.f = f\n",
    "        self.memo = {}\n",
    "\n",
    "    def __call__(self, *args):\n",
    "        key = json.dumps(args)\n",
    "        if not key in self.memo:\n",
    "            self.memo[key] = self.f(*args)\n",
    "        return self.memo[key]\n",
    "\n",
    "@memoize\n",
    "def stole_max(c, money_list):\n",
    "    if c > len(money_list) - 1:\n",
    "        return 0\n",
    "    elif c == len(money_list) - 1:\n",
    "        return money_list[c]\n",
    "    elif c == len(money_list) - 2:\n",
    "        return max(money_list[c], money_list[c + 1])\n",
    "    else:\n",
    "        return max(money_list[c] + stole_max(c + 2, money_list),\n",
    "                   money_list[c + 1] + stole_max(c + 3, money_list))\n",
    "\n",
    "\n",
    "def stole_max_new(money_list):\n",
    "    if len(money_list) == 1:\n",
    "        return money_list[0]\n",
    "\n",
    "    money_list_copy = money_list.copy()\n",
    "    money_list_copy.pop(-1)\n",
    "    return max(stole_max(1, money_list), stole_max(0, money_list_copy))\n",
    "\n",
    "class Solution(object):\n",
    "    def rob(self, nums):\n",
    "        return stole_max_new(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 3:\n",
    "            return max(nums)\n",
    "        \n",
    "        nums1 = nums[: -1]\n",
    "        nums2 = nums[1:]\n",
    "        # print(nums2)\n",
    "        dp1 = [0] * (len(nums))\n",
    "        dp2 = [0] * (len(nums))\n",
    "        dp1[1] = nums1[0]\n",
    "        dp2[1] = nums2[0]\n",
    "        # print(dp2[1])\n",
    "\n",
    "        for i in range(1, len(nums1) + 1):\n",
    "            num1 = nums1[i - 1]\n",
    "            dp1[i] = max(dp1[i - 1], dp1[i - 2] + num1)\n",
    "        \n",
    "        for j in range(1, len(nums2) + 1):\n",
    "            num2 = nums2[j - 1]\n",
    "            dp2[j] = max(dp2[j - 1], dp2[j - 2] + num2)\n",
    "            # print(dp2)\n",
    "        return dp1[-1] if dp1[-1] > dp2[-1] else dp2[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        def rob_value(sub_nums):\n",
    "            pre, cur = 0, 0\n",
    "            for num in sub_nums:\n",
    "                cur, pre = max(pre+num, cur), cur\n",
    "            return cur\n",
    "\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        value1 = rob_value(nums[:len(nums)-1])\n",
    "        # print(nums[:len(nums)-1])\n",
    "        value2 = rob_value(nums[1:])\n",
    "        # print(value2)\n",
    "        return max(value1,value2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def helper(self,nums):\n",
    "        size=len(nums)\n",
    "        if size==1:\n",
    "            return nums[0]\n",
    "        elif size==2:\n",
    "            return max(nums[0],nums[1])\n",
    "        dp=[0 for _ in range(size)]\n",
    "        dp[0]=nums[0]\n",
    "        dp[1]=max(nums[0],nums[1])\n",
    "        for i in range(2,size):\n",
    "            dp[i]=max(dp[i-2]+nums[i],dp[i-1])\n",
    "        return dp[size-1]\n",
    "\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        size=len(nums)\n",
    "        if size==0:\n",
    "            return 0\n",
    "        elif size==1:\n",
    "            return nums[0]\n",
    "        elif size==2:\n",
    "            return max(nums[0],nums[1])\n",
    "        return max(self.helper(nums[:size-1]),self.helper(nums[1:size]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        if len(nums)==2:\n",
    "            return max(nums[0],nums[1])\n",
    "        return max(self.rob_method(nums[1:]),self.rob_method(nums[:len(nums)-1]))\n",
    "\n",
    "    def rob_method(self,nums):\n",
    "        dp = [0]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[1],nums[0])\n",
    "        for i in range(2,len(nums)):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        return max(dp[-1],dp[-2])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1:return nums[0]\n",
    "        @cache\n",
    "        def dfs(i,last):\n",
    "            if i<0:return 0\n",
    "            if last and i==0:return 0\n",
    "            tmp = max(dfs(i-1,last),dfs(i-2,last)+nums[i])\n",
    "            return tmp\n",
    "        return max(dfs(n-1,True),dfs(n-2,False))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return max(nums)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        dp[0][0] = nums[0]\n",
    "        dp[0][1] = max(nums[0],nums[1])\n",
    "        dp[1][1] = nums[1]\n",
    "        for i in range(n):\n",
    "            for j in range(2,n):\n",
    "                if i>j:\n",
    "                    dp[i][j] = float('-inf')\n",
    "                elif i == j:\n",
    "                    dp[i][i] = nums[i]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i][j-2]+nums[j] if (i>0 or j < n-1) else float('-inf'))\n",
    "        return max(dp[i][n-1] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "\n",
    "            return max(nums[0],self.helper(nums[1:]), self.helper(nums[:-1]))\n",
    "\n",
    "    def helper(self, nums):\n",
    "        rob1,rob2=0,0\n",
    "        for n in nums:\n",
    "            temp=max(rob1+n,rob2)\n",
    "            rob1=rob2\n",
    "            rob2=temp\n",
    "        return rob2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getmaxmoney(self,nums):\n",
    "        if len(nums)<1:return 0\n",
    "        elif len(nums)<2:return nums[0]\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0],nums[1])\n",
    "        for i in range(2,len(nums)):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        return dp[len(nums)-1]\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 1:\n",
    "            return 0\n",
    "        elif len(nums) < 2:\n",
    "            return nums[0]\n",
    "        return max(self.getmaxmoney(nums[:-1]),self.getmaxmoney(nums[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        def rob1(nums: List[int]) -> int:\n",
    "            f0 = f1 = 0\n",
    "            for n in nums:\n",
    "                f0, f1 = f1, max(f1, f0 + n)\n",
    "            \n",
    "            return f1\n",
    "        \n",
    "        return max(nums[0] + rob1(nums[2:-1]), rob1(nums[1:]))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
